Нигде не нулевой поток

Нигде не нулевой поток в теории графов — специальный вид сетевого потока, который связан (двойственностью) с раскраской планарных графов.

Определение

Пусть G = (V,E) — ориентированный граф и пусть M — абелева группа. Отображение φ: E → M называется потоком или M-потоком, если для любой вершины v ∈ V, выполняется

$\sum _{e\in \delta ^{+}(v)}\phi (e)=\sum _{e\in \delta ^{-}(v)}\phi (e),$

где δ⁺(v) обозначает множество исходящих из v рёбер, а δ^-(v) — множество входящих в v. Иногда это условие трактуется как правило Кирхгофа. Если φ(e) ≠ 0 для любой вершины e ∈ E, мы говорим о φ как о нигде не нулевом потоке. Если M = Z — группа целых чисел по сложению и k — положительное число, такое что -k < φ(e) < k для любого ребра e, то M-поток φ называют также k-потоком.

Пусть G = (V,E) — ненаправленный граф. Ориентация дуг в E называется модульным k-потоком, если

$|\delta ^{+}(v)|\equiv |\delta ^{-}(v)|{\pmod {k}}$

для всех вершин v ∈ V.

Свойства

Изменим нигде не нулевой поток φ на графе G путём выбора дуги e, изменения направления дуги и замены φ(e) на -φ(e). После таких изменений поток останется нигде не нулевым. Далее, если φ был первоначально k-потоком, то и результирующий поток таковым останется. Таким образом, существование нигде не нулевого M-потока или k-потока не зависит от направлений дуг графа. Мы можем сказать, что неориентированный граф G имеет нигде не нулевой M- поток или k- поток, если какая-либо (а значит и любая) ориентация дуг графа G имеет такой поток.

Ещё более удивительно то, что если M является конечной абелевой группой размера k, то число нигде не нулевых M-потоков на некоторых графах не зависит от структуры M, а только от k, размера M. Более того, существование M-потока совпадает с существованием k-потока. Эти два результата доказаны Таттом в 1953 году.

Двойственность потоков и раскраски

Пусть G = (V,E) — ориентированный граф без мостов, нарисованный на плоскости, и предположим, что области (грани) правильно раскрашены в k цветов {0, 1, 2, .., k — 1}. Построим отображение φ: E(G) → {-(k — 1), …, −1, 0, 1, …, k — 1} по следующему правилу: если дуга e имеет цвет x слева и цвет y справа, положим φ(e) = x — y. Легко проверить, что φ — k-поток. Более того, если области выкрашены правильно, φ нигде не нулевой k-поток. Это следует из построения, поскольку если G и G* планарные двойственные графы и G* — k-раскрашиваем, то G имеет нигде не нулевой k-поток. Татт доказал, что обратное этому утверждению тоже верно. Таким образом, для планарных графов нигде не нулевые потоки являются двойственными раскраске. Поскольку нигде не нулевые потоки имеют смысл для произвольных графов (не только для тех, что можно нарисовать на плоскости), их изучение можно рассматривать как расширение теории раскраски на непланарные графы.

Теория

Нерешённые проблемы математики: Имеет ли произвольный граф без мостов нигде не нулевой 5-поток? Имеет ли произвольный граф без мостов и без графов Петерсена в качестве миноров нигде не нулевой 4-поток?

Поскольку никакой граф с петлёй не имеет правильной раскраски, никакой граф, имеющий мосты, не может иметь нигде не нулевой поток (в любой группе). Легко показать, что любой граф без мостов имеет нигде не нулевой Z-поток (из теоремы Роббинса), но интересный вопрос возникает при попытке найти нигде не нулевой k-поток для малых значений k. Две элегантные теоремы в этом направлении — теорема Джагера о 4-потоке (любой рёберно 4-связный граф имеет нигде не нулевой 4-поток) и теорема Сеймура о 6-потоке (любой граф без мостов имеет нигде не нулевой 6-поток).

Татт высказал гипотезу, что любой граф без мостов имеет нигде не нулевой 5-поток и что любой граф без мостов, не содержащий граф Петерсена в качестве минора имеет нигде не нулевой 4-поток. Для кубических графов, не содержащих минор Петерсена, существование 4-потока следует из теоремы о снарках, но для произвольных графов гипотеза остаётся открытой.

См. также

• Пространство циклов

Ссылки

• Cun-Quan Zhang. Integer Flows and Cycle Covers of Graphs. — Marcel Dekker, Inc., 1997. — (Chapman & Hall/CRC Pure and Applied Mathematics Series). — ISBN 9780824797904.
• Cun-Quan Zhang. Circuit Double Cover of Graphs. — Cambridge University Press, 2012. — ISBN 978-0-5212-8235-2.
• T.R. Jensen and B. Toft, Graph Coloring Problems, Wiley-Interscience Serires in Discrete Mathematics and Optimization, (1995)